package code;

import java.util.ArrayList;
import java.util.List;


public class Sum3 {

	public int mergeSort(int l,int r,int[] array){
		if(l==r){
			return 0;
		}
		int mid=l+r>>1;
		int lcnt=mergeSort(l,mid,array);
		int rcnt=mergeSort(mid+1,r,array);
		int sum=lcnt+rcnt;
		int[] tmp=new int[r-l+1];
		int idx=0;
		int i,j;
		for(i=l,j=mid+1;i<=mid && j<=r;){
			if(array[i]>array[j]){
				sum++;
				tmp[idx++]=array[j];
				j++;
			}
			else{
				tmp[idx++]=array[i];
				i++;
			}
		}
		for(;i<=mid;i++)	tmp[idx++]=array[i];
		for(;j<=r;j++)	tmp[idx++]=array[j];
		for(i=0;i<r-l+1;i++)
			array[l+i]=tmp[i];
		return sum;
	}
	
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        int n=num.length;
        if(n<3)	return result;
        mergeSort(0, n-1, num);
        int i,j,k;
        for(i=0;i<n;i++){
        	if(i>0 && num[i]==num[i-1])	continue;
        	j=i+1;
        	k=n-1;
        	while(j<k){
        		if(j-1>i && num[j]==num[j-1]) j++;
        		if(k-1>j && num[k]==num[k-1]) k--;
        		int sum=num[i]+num[j]+num[k];
        		if(sum==0){
        			List<Integer> list=new ArrayList<Integer>();
        			list.add(num[i]);
        			list.add(num[j]);
        			list.add(num[k]);
        			System.out.println(num[i]+" "+num[j]+" "+num[k]);
        			result.add(list);
        			j++;
        		}
        		else if(sum>0)	k--;
        		else j++;
        	}
        }
        
        return result;
    }
    public static void main(String[] args){
    	int[] num={-1,0,1,2,-1,-4};
    	int[] num2={7,-1,14,-12,-8,7,2,-15,8,8,-8,-14,-4,-5,7,9,11,-4,-15,-6,1,-14,4,3,10,-5,2,1,6,11,2,-2,-5,-7,-6,2,-15,11,-6,8,-4,2,1,-1,4,-6,-15,1,5,-15,10,14,9,-8,-6,4,-6,11,12,-15,7,-1,-9,9,-1,0,-4,-1,-12,-2,14,-9,7,0,-3,-4,1,-2,12,14,-10,0,5,14,-1,14,3,8,10,-8,8,-5,-2,6,-11,12,13,-7,-12,8,6,-13,14,-2,-5,-11,1,3,-6};
    	int[] num3={12,-14,-5,12,-2,9,0,9,-3,-3,-14,-6,-4,13,-11,-8,0,5,-7,-6,-10,-13,-7,-14,-3,0,12,5,-8,7,3,-11,0,6,9,13,-8,-6,7,4,6,0,13,-13,-1,9,-13,6,-1,-13,-15,-4,-11,-15,-11,-7,1,-14,13,8,0,2,4,-15,-15,-2,5,-8,7,-11,11,-10,4,1,-15,10,-5,-13,2,1,11,-6,4,-15,-5,8,-7,3,1,-9,-4,-14,0,-15,8,0,-1,-2,7,13,2,-5,11,13,11,11};
    	new Sum3().threeSum(num3);
    }
}
